home *** CD-ROM | disk | FTP | other *** search
/ Internet Surfer 2.0 / Internet Surfer 2.0 (Wayzata Technology) (1996).iso / pc / text / mac / faqs.454 < prev    next >
Text File  |  1996-02-12  |  28KB  |  795 lines
  1. Frequently Asked Questions (FAQS);faqs.454
  2.  
  3.  
  4.  
  5.    State         Symbol  New     Symbol  New      Symbol   New
  6.         Accept?         State           State             State
  7.  
  8. --> [0#0]  Y       8:2  [0#3]      0:0  [0#0]         0   [A]
  9.     [0#3]  N       7:1  [3#3]
  10.     [3#3]  Y       1:7  [3#0]      9:9  [3#3]         9   [A]
  11.     [3#0]  N       2:8  [0#0]
  12.      [A]   Y
  13.  
  14. for constant C=4, and
  15.  
  16.    State         Symbol  New     Symbol  New      Symbol   New
  17.         Accept?         State           State             State
  18.  
  19. --> [0#0]  Y       1:9  [0#8]      0:0  [0#0]         0   [A]
  20.     [0#8]  N       8:0  [8#8]
  21.     [8#8]  Y       0:8  [8#0]      9:9  [8#8]         9   [A]
  22.     [8#0]  N       9:1  [0#0]
  23.      [A]   Y
  24.  
  25. for constant C=9, and the finite state machines for other constants
  26. accept only strings of zeroes.  It is not hard to verify that the
  27. proposed regular expression (1) represents the union of the languages
  28. accepted by these machines, omitting the empty string and strings
  29. beginning with zero.
  30.  
  31. I have written a computer program that constructs finite state
  32. machines for recognizing palintiples for various bases and constants.
  33. I found that base 10 is actually an unusually boring base for this
  34. problem.  For instance, the machine for base 8, constant C=5 is
  35.  
  36.    State         Symbol  New     Symbol  New      Symbol  New
  37.         Accept?         State           State            State
  38.  
  39. --> [0#0]  Y       0:0  [0#0]      5:1  [0#3]         0  [A]
  40.     [0#3]  N       1:0  [1#1]      6:1  [1#4]
  41.     [1#1]  Y       0:1  [3#0]      5:2  [3#3]
  42.     [3#0]  N       1:5  [0#0]      6:6  [0#3]         6  [A]
  43.     [3#3]  Y       2:5  [1#1]      7:6  [1#4]
  44.     [1#4]  N       1:1  [4#1]      6:2  [4#4]         1  [A]
  45.     [4#4]  Y       2:6  [4#1]      7:7  [4#4]         7  [A]
  46.     [4#1]  N       1:6  [3#0]      6:7  [3#3]
  47.      [A]   Y
  48.  
  49. for which I invite masochists to write the regular expression.  If
  50. anyone wants more, I should remark that the base 29 machine for
  51. constant C=18 has 71 states!
  52.  
  53. By the way, I did not find any way of predicting the size or form of
  54. the machines for the various bases, except that the machines for C=B-1
  55. all seem to be isomorphic to each other.  If anyone investigates the
  56. general behavior, I would be most happy to hear about it.
  57.  
  58. Dan Hoey
  59. Hoey@AIC.NRL.Navy.Mil
  60. May, 1992
  61. [ A preliminary version of this message appeared in April, 1991. ]
  62. ================================================================
  63. Dan
  64.  
  65.  
  66.  
  67. ==> arithmetic/digits/power.two.p <==
  68. Prove that for any 9-digit number (base 10) there is an integral power
  69. of 2 whose first 9 digits are that number.
  70.  
  71. ==> arithmetic/digits/power.two.s <==
  72. Let v = log to base 10 of 2.
  73. Then v is irrational.
  74.  
  75. Let w = log to base 10 of these 9 digits.
  76.  
  77. Since v is irrational, given epsilon > 0, there exists some natural number
  78. n such that
  79.  
  80.    {w} < {nv} < {w} + epsilon
  81.  
  82. ({x} is the fractional part of x.)  Let us pick n for when
  83.  
  84.    epsilon = log 1.00000000000000000000001.
  85.  
  86. Then 2^n does the job.
  87.  
  88. ==> arithmetic/digits/prime/101.p <==
  89. How many primes are in the sequence 101, 10101, 1010101, ...?
  90.  
  91. ==> arithmetic/digits/prime/101.s <==
  92. Note that the sequence
  93. 101 , 10101, 1010101, ....
  94. can be viewed as
  95. 100**1 +1, 100**2 + 100**1 + 1, 100**3 + 100**2 + 100**1 +1 ....
  96. that is,
  97. the k-th term in the sequence is
  98. 100**k + 100**(k-1) + 100**(k-2) + ...+ 100**(1) + 1
  99. = (100)**(k+1) - 1
  100.   ----------------
  101.     11 * 9
  102. = (10)**(2k+2) - 1
  103.   ----------------
  104.     11 * 9
  105. = ((10)**(k+1) - 1)*((10)**(k+1) +1)
  106.    ---------------------------------
  107.        11*9
  108. thus either 11 and 9 divide the numerator. Either they both divide the
  109. same factor in the numerator or different factors in the numerator. In
  110. any case, after dividing, they leave the numerators as a product of two
  111. integers.  Only in the case of k = 1, one of the integers is 1. Thus
  112. there is exactly one prime in the above sequence: 101.
  113.  
  114. ==> arithmetic/digits/prime/all.prefix.p <==
  115. What is the longest prime whose every proper prefix is a prime?
  116.  
  117. ==> arithmetic/digits/prime/all.prefix.s <==
  118. 23399339, 29399999, 37337999, 59393339, 73939133
  119.  
  120. ==> arithmetic/digits/prime/change.one.p <==
  121. What is the smallest number that cannot be made prime by changing a single
  122. digit?  Are there infinitely many such numbers?
  123.  
  124. ==> arithmetic/digits/prime/change.one.s <==
  125. 200.  Obviously, you would have to change the last digit, but 201, 203,
  126. 207, and 209 are all composite.  For any smaller number, you can change
  127. the last digit, and get
  128. 2,11,23,31,41,53,61,71,83,97,101,113,127,131,149,151,163,173,181, or 191.
  129.  
  130. 200+2310n gives an infinite family, because changing the last
  131. digit to 1 or 7 gives a number divisible by 3; to 3, a number divisible
  132. by 7; to 9, a number divisible by 11.
  133.  
  134. ==> arithmetic/digits/prime/prefix.one.p <==
  135. 2 is prime, but 12, 22, ..., 92 are not.  Similarly, 5 is prime
  136. whereas 15, 25, ..., 95 are not.  What is the next prime number
  137. which is composite when any digit is prefixed?
  138.  
  139. ==> arithmetic/digits/prime/prefix.one.s <==
  140. 149
  141.  
  142. ==> arithmetic/digits/reverse.p <==
  143. Is there an integer that has its digits reversed after dividing it by 2?
  144.  
  145. ==> arithmetic/digits/reverse.s <==
  146. Assume there's such a positive integer x such that x/2=y and y is the
  147. reverse of x.
  148.  
  149. Then x=2y.  Let x = a...b, then y = b...a, and:
  150.  
  151.                  b...a   (y)
  152.            x     2
  153.                --------
  154.                  a...b   (x)
  155.  
  156. From the last digit b of x, we have b = 2a (mod 10), the possible
  157. values for b are 2, 4, 6, 8 and hence possible values for (a, b) are
  158. (1,2), (6,2), (2,4), (7,4), (3,6), (8,6), (4,8), (9,8).
  159.  
  160. From the first digit a of x, we have a = 2b or a = 2b+1.  None of the
  161. above pairs satisfy this condition.  A contradiction.
  162.  
  163. Hence there's no such integer.
  164.  
  165. ==> arithmetic/digits/rotate.p <==
  166. Find integers where multiplying them by single digits rotates their digits.
  167.  
  168. ==> arithmetic/digits/rotate.s <==
  169. 2 105263157894736842
  170. 3 1034482758620689655172413793
  171. 4 102564 153846 179487 205128 230769
  172. 5 142857 102040816326530612244897959183673469387755
  173. 6 1016949152542372881355932203389830508474576271186440677966
  174.   1186440677966101694915254237288135593220338983050847457627
  175.   1355932203389830508474576271186440677966101694915254237288
  176.   1525423728813559322033898305084745762711864406779661016949
  177. 7 1014492753623188405797 1159420289855072463768 1304347826086956521739
  178. 8 1012658227848 1139240506329
  179. 9 10112359550561797752808988764044943820224719
  180.  
  181. In base B, suppose you have an N-digit answer A whose digits are
  182. rotated when multiplied by K.  If D is the low-order digit of A, we
  183. have
  184.  
  185.     (A-D)/B + D B^(N-1) = K A .
  186.  
  187. Solving this for A we have
  188.  
  189.         D (B^N - 1)
  190.     A = ----------- .
  191.           B K - 1
  192.  
  193. In order for A >= B^(N-1) we must have D >= K.  Now we have to find N
  194. such that B^N-1 is divisible by R=(BK-1)/gcd(BK-1,D).  This always has
  195. a minimal solution N0(R,B)<R, and the set of all solutions is the set
  196. of multiples of N0(R,B).  N0(R,B) is the length of the repeating part
  197. of the fraction 1/R in base B.
  198.  
  199. N0(ST,B)=N0(S,B)N0(T,B) when (S,T)=1, and for prime powers, N0(P^X,B)
  200. divides (P-1)P^(X-1). Determining which divisor is a little more
  201. complicated but well-known (cf. Hardy & Wright).
  202.  
  203. So given B and K, there is one minimal solution for each
  204. D=K,K+1,...,B-1, and you get all the solutions by taking repetitions
  205. of the minimal solutions.
  206.  
  207. ==> arithmetic/digits/sesqui.p <==
  208. Find the least number where moving the first digit to the end multiplies by 1.5.
  209.  
  210. Xref: bloom-picayune.mit.edu rec.puzzles:18138 news.answers:3070
  211. Newsgroups: rec.puzzles,news.answers
  212. Path: bloom-picayune.mit.edu!snorkelwacker.mit.edu!spool.mu.edu!uunet!questrel!chris
  213. From: uunet!questrel!chris (Chris Cole)
  214. Subject: rec.puzzles FAQ, part 3 of 15
  215. Message-ID: <puzzles-faq-3_717034101@questrel.com>
  216. Followup-To: rec.puzzles
  217. Summary: This posting contains a list of
  218.      Frequently Asked Questions (and their answers).
  219.      It should be read by anyone who wishes to
  220.      post to the rec.puzzles newsgroup.
  221. Sender: chris@questrel.com (Chris Cole)
  222. Reply-To: uunet!questrel!faql-comment
  223. Organization: Questrel, Inc.
  224. References: <puzzles-faq-1_717034101@questrel.com>
  225. Date: Mon, 21 Sep 1992 00:08:46 GMT
  226. Approved: news-answers-request@MIT.Edu
  227. Expires: Sat, 3 Apr 1993 00:08:21 GMT
  228. Lines: 1353
  229.  
  230. Archive-name: puzzles-faq/part03
  231. Last-modified: 1992/09/20
  232. Version: 3
  233.  
  234. ==> arithmetic/digits/sesqui.s <==
  235. Let's represent this number as  a*10^n+b,  where 1<=a<=9 and
  236. b < 10^n.  Then the condition to be satisfied is:
  237.  
  238. 3/2(a*10^n+b) = 10b+a
  239.  
  240.   3(a*10^n+b) = 20b+2a
  241.  
  242.    3a*10^n+3b = 20b+2a
  243.  
  244.   (3*10^n-2)a = 17b
  245.  
  246.             b = a*(3*10^n-2)/17
  247.  
  248. So we must have 3*10^n-2 = 0 (mod 17) (since a is less than 10, it
  249. cannot contribute the needed prime 17 to the factorization of 17b).
  250. (Also, assuming large n, we must have a at most 5 so that b < 10^n will
  251. be satisfied, but note that we can choose a=1).  Now,
  252.  
  253. 3*10^n-2 = 0 (mod 17)
  254.  
  255. 3*10^n = 2 (mod 17)
  256.  
  257. 10^n = 12 (mod 17)
  258.  
  259. A quick check shows that the smallest n which satisfies this is 15
  260. (the fact that one exists was assured to us because 17 is prime).  So,
  261. setting n=15 and a=1 (obviously) gives us b=176470588235294, so the
  262. number we are looking for is
  263.  
  264.                         1176470588235294
  265.  
  266. and, by the way, we can set a=2 to give us the second smallest such
  267. number,
  268.                         2352941176470588
  269.  
  270. Other things we can infer about these numbers is that there are 5 of
  271. them less than 10^16, 5 more less than 10^33, etc.
  272.  
  273. ==> arithmetic/digits/squares/leading.7.to.8.p <==
  274. What is the smallest square with leading digit 7 which remains a square
  275. when leading 7 is replaced by an 8?
  276.  
  277. ==> arithmetic/digits/squares/leading.7.to.8.s <==
  278. x=2996282391593370361328125
  279. y=2824483699753370361328125
  280. x^2=8977708170172487211329625006796419620513916015625
  281. y^2=7977708170172487211329625006796419620513916015625
  282.  
  283. ==> arithmetic/digits/squares/length.22.p <==
  284. Is it possible to form two numbers A and B from 22 digits such that
  285. A = B^2?  Of course, leading digits must be non-zero.
  286.  
  287. ==> arithmetic/digits/squares/length.22.s <==
  288. No, the number of digits of A^2 must be of the form 3n or 3n-1.
  289.  
  290. ==> arithmetic/digits/squares/length.9.p <==
  291. Is it possible to make a number and its square, using the digits from 1 through
  292. 9 exactly once?
  293.  
  294. ==> arithmetic/digits/squares/length.9.s <==
  295. 567 and 854.
  296.  
  297. ==> arithmetic/digits/squares/three.digits.p <==
  298. What squares consist entirely of three digits (e.g., 1, 4, and 9)?
  299.  
  300. ==> arithmetic/digits/squares/three.digits.s <==
  301. The full set of solutions up to 10**12 is
  302.               1 ->                            1
  303.               2 ->                            4
  304.               3 ->                            9
  305.               7 ->                           49
  306.              12 ->                          144
  307.              21 ->                          441
  308.              38 ->                         1444
  309.             107 ->                        11449
  310.             212 ->                        44944
  311.           31488 ->                   9914 94144
  312.           70107 ->                  49149 91449
  313.         3 87288 ->               14 99919 94944
  314.       956 10729 ->          9 14141 14499 11441
  315.      4466 53271 ->        199 49914 44949 99441
  316.     31487 17107 ->       9914 41941 99144 49449
  317.   2 10810 79479 ->    4 44411 91199 99149 11441
  318.  
  319. If the algorithm is used in the form I presented it before, generating
  320. the whole set P_n before starting on P_{n+1}, the store requirements
  321. begin to become embarassing. For n>8 I switched to a depth-first
  322. strategy, generating all the elements in P_i (i=9..12) congruent to
  323. a particular x in P_8 for each x in turn. This means the solutions
  324. don't come out in any particular order, of course. CPU time was 16.2
  325. seconds (IBM 3084).
  326.  
  327. In article <1990Feb6.025205.28153@sun.soe.clarkson.edu>, Steven
  328. Stadnicki suggests alternate triples of digits, in particular {1,4,6}
  329. (with many solutions) and {2,4,8} (with few). I ran my program on
  330. these as well, up to 10**12 again:
  331.               1 ->                            1
  332.               2 ->                            4
  333.               4 ->                           16
  334.               8 ->                           64
  335.              12 ->                          144
  336.              21 ->                          441
  337.              38 ->                         1444
  338.             108 ->                        11664
  339.             119 ->                        14161
  340.             121 ->                        14641
  341.             129 ->                        16641
  342.             204 ->                        41616
  343.             408 ->                      1 66464
  344.             804 ->                      6 46416
  345.            2538 ->                     64 41444
  346.            3408 ->                    116 14464
  347.            6642 ->                    441 16164
  348.           12908 ->                   1666 16464
  349.           25771 ->                   6641 44441
  350.           78196 ->                  61146 14416
  351.           81619 ->                  66616 61161
  352.         3 33858 ->               11 14611 64164
  353.      2040 00408 ->         41 61616 64641 66464
  354.      6681 64962 ->        446 44441 64444 61444
  355.      8131 18358 ->        661 16146 41166 16164
  356.     40182 85038 ->      16146 61464 66146 61444  (Steven's last soln.)
  357.   1 20068 50738 ->    1 44164 46464 46111 44644
  358.   1 26941 38988 ->    1 61141 16464 66616 64144
  359.   1 27069 43631 ->    1 61466 41644 14114 64161
  360.   4 01822 24262 ->   16 14611 14664 16614 44644
  361.   4 05784 63021 ->   16 46611 66114 66644 46441
  362.  78 51539 12392 -> 6164 66666 14446 44111 61664
  363. and
  364.               2 ->                            4
  365.              22 ->                          484
  366.             168 ->                        28224
  367.             478 ->                      2 28484
  368.            2878 ->                     82 82884 (Steven's last soln.)
  369.      2109 12978 ->         44 48428 42888 28484
  370. (so the answer to Steven's "Are there any more at all?" is "Yes".)
  371.  
  372. The CPU times were 42.9 seconds for {1,4,6}, 18.7 for {2,4,8}. This
  373. corresponds to an interesting point: the abundance of solutions for
  374. {1,4,6} is associated with abnormally large sets P_n (|P_8| = 16088
  375. for {1,4,6} compared to |P_8| = 5904 for {1,4,9}) but the deficiency
  376. of solutions for {2,4,8} is *not* associated with small P_n's (|P_8|
  377. = 6816 for {2,4,8}). Can anyone wave a hand convincingly to explain
  378. why the solutions for {2,4,8} are so sparse?
  379.  
  380. I suspect we are now getting to the point where an improved algorithm
  381. is called for. The time to determine all the n-digit solutions (i.e.
  382. 2n-digit squares) using this last-significant-digit-first is essentially
  383. constant * 3**n. Dean Hickerson in <90036.134503HUL@PSUVM.BITNET>, and
  384. Ilan Vardi in <1990Feb5.214249.22811@Neon.Stanford.EDU>, suggest using
  385. a most-significant-digit-first strategy, based on the fact that the
  386. first n digits of the square determine the (integral) square root; this
  387. also has a running time constant * 3**n. Can one attack both ends at
  388. once and do better?
  389.  
  390. Chris Thompson
  391. JANET:    cet1@uk.ac.cam.phx
  392. Internet: cet1%phx.cam.ac.uk@nsfnet-relay.ac.uk
  393.  
  394. Hey guys, what about
  395.  
  396. 648070211589107021 ^ 2 = 419994999149149944149149944191494441
  397.  
  398. This was found by David Applegate and myself (about 5 minutes on a DEC 3100,
  399. program in C).
  400.  
  401. This is the largest square less than 10^42 with the 149-property; checking
  402. took a bit more than an hour of CPU time.
  403.  
  404. As somebody suggested, we used a combined most-significant/least-significant
  405. digits attack.  First we make a table of p-digit prefixes (most significant
  406. p digits) that could begin a root whose square has the 149 property in its
  407. first p digits.  We organize this table into buckets by the least
  408. significant q digits of the prefixes.  Then we enumerate the s digit
  409. suffixes whose squares have the 149 property in their last s digits.  For
  410. each such suffix, we look in the table for those prefixes whose last q
  411. digits match the first q of the suffix.  For each match, we consider the p +
  412. s - q digit number formed by overlapping the prefix and the suffix by q
  413. digits.  The squares of these overlap numbers must contain all the squares
  414. with the 149 property.
  415.  
  416. The time expended is O(3^p) to generate the prefix table, O(3^s) to
  417. enumerate the suffixes, and O(3^(p+s) / 10^q) to check the overlaps (being
  418. very rough and ignoring the polynomial factors) By judiciously chosing p, q,
  419. and s, we can fix things so that each bucket of the table has around O(1)
  420. entries: set q = p log10(3).  Setting p = s, we end up looking for squares
  421. whose roots have n = 2 - log10(3) digits, with an algorithm that takes time
  422. O( 3 ^ [n / (2 - log10(3)]) ), roughly time O(3^[.66n]).  Compared to the
  423. O(3^n) performance of either single-ended algorithm, this lets us check 50%
  424. more digits in the same amount of time (ignoring polynomial factors).  Of
  425. course, the space cost of the combined-ends method is high.
  426.  
  427. -- Guy and Dave
  428. --
  429. Guy Jacobson              School of Computer Science
  430. Carnegie Mellon     arpanet : guy@cs.cmu.edu
  431. Pittsburgh, PA  15213    csnet   : Guy.Jacobson%a.cs.cmu.edu@csnet-relay
  432. (412) 268-3056        uucp    : ...!{seismo, ucbvax, harvard}!cs.cmu.edu!guy
  433.  
  434. Here is an algorithm which takes O(sqrt(n)log(n)) steps to find all perfect
  435. squares < n whose only digits are 1, 4 and 9.
  436.  
  437. This doesn't sound too great *but* it doesn't use a lot of memory and only
  438. requires addition and <.  Also, the actual run time will depend on where the
  439. first non-{1,4,9} digit appears in each square.
  440.  
  441.     set n = 1
  442.     set odd = 1
  443.  
  444.     while(n < MAXVAL)
  445.     {
  446.         if(all digits of n are in {1,4,9})
  447.         {
  448.             print n
  449.         }
  450.  
  451.         add 2 to odd
  452.         add odd to n
  453.     }
  454.  
  455. This works because (X+1)^2 - x^2 = 2x+1.
  456. That is, if you start with 0 and add successive odd
  457. numbers to it you get 0+1=1, 1+3=4, 4+5=9, 9+7=16 etc.
  458. I've started the algorithm at 1 for convenience.
  459.  
  460. The "O" value comes from looking at at most all digits
  461. (log(n)) of all perfect squares < n (sqrt(n) of them)
  462. at most a constant number of times.
  463.  
  464. I didn't save the articles with algorithms claiming to be
  465. O(3^log(n)) so I don't know if their calculations needed
  466. to (or did) account for multiplication or sqrt() of large
  467. numbers.  O(3^log(n)) sounds reasonable so I'm going to
  468. assume they did unless I hear otherwise.
  469.  
  470. Any comments? Please email if you just want to refresh my memory
  471. on the other algorithms.
  472.  
  473. Andrew Charles
  474. acgd@ihuxy.ATT.COMM
  475.  
  476. ==> arithmetic/digits/squares/twin.p <==
  477. Let a twin be a number formed by writing the same number twice,
  478. for instance, 81708170 or 132132.  What is the smallest square twin?
  479.  
  480. ==> arithmetic/digits/squares/twin.s <==
  481. 1322314049613223140496 = 36363636364 ^ 2.
  482.  
  483. The key to solving this puzzle is looking at the basic form of these
  484. "twin" numbers, which is some number k = 1 + 10^n multiplied by some number
  485. a < 10^n. If ak is a perfect square, k must have some repeated factor,
  486. since a<k. Searching the possible values of k for one with a repeated factor
  487. eventually turns up the number 1 + 10^11 = 11^2 * 826446281.
  488. So, we set a=826446281 and ak = 9090909091^2 = 82644628100826446281,
  489. but this needs leading zeros to fit the pattern. So, we multiply by a suitable
  490. small square (in this case 16) to get the above answer.
  491.  
  492. ==> arithmetic/digits/sum.of.digits.p <==
  493. Find sod ( sod ( sod (4444 ^ 4444 ) ) ).
  494.  
  495. ==> arithmetic/digits/sum.of.digits.s <==
  496. let X = 4444^4444
  497.  
  498. sod(X) <= 9 * (# of digits) < 145900
  499. sod(sod(X)) <= sod(99999) = 45
  500. sod(sod(sod(X))) <= sod(39) = 12
  501.  
  502. but sod(sod(sod(X))) = 7 (mod 9)
  503.  
  504. thus sod(sod(sod(X))) = 7
  505.  
  506. ==> arithmetic/digits/zeros/factorial.p <==
  507. How many zeros are in the decimal expansion of n!?
  508.  
  509. ==> arithmetic/digits/zeros/factorial.s <==
  510. The general answer to the question
  511. "what power of p divides x!" where p is prime
  512. is (x-d)/(p-1) where d is the sum of the digits of (x written in base p).
  513.  
  514. So where p=5, 10 is written as 20 and is divisible by 5^2 (2 = (10-2)/4);
  515. x to base 10:     100    1000    10000    100000     1000000
  516. x to base 5:      400   13000   310000  11200000   224000000
  517. d          :        4       4        4         4           8
  518. trailing 0s in x!  24     249     2499     24999      249998
  519.  
  520. ==> arithmetic/digits/zeros/lsd.factorial.p <==
  521. What is the least significant non-zero digit in the decimal expansion of n!?
  522.  
  523. ==> arithmetic/digits/zeros/lsd.factorial.s <==
  524. Reduce mod 10 the numbers 2..n and then cancel out the
  525. required factors of 10. The final step then involves
  526. computing 2^i*3^j*7^k mod 10 for suitable i,j and k.
  527.  
  528. A small program that performs this calculation is appended. Like the
  529. other solutions, it takes O(log n) arithmetic operations.
  530.  
  531. -kym
  532. ===
  533.  
  534. #include<stdio.h>
  535. #include<assert.h>
  536.  
  537. int    p[6][4]={
  538.     /*2*/    2,    4,    8,    6,
  539.     /*3*/    3,    9,    7,    1,
  540.     /*4*/    4,    6,    4,    6,
  541.     /*5*/    5,    5,    5,    5,
  542.     /*6*/    6,    6,    6,    6,
  543.     /*7*/    7,    9,    3,    1,
  544.     };
  545.  
  546. main(){
  547.     int    i;
  548.     int n;
  549.  
  550.     for(n=2;n<1000;n++){
  551.         i=lsdfact(n);
  552.         printf("%d\n",i);
  553.         }
  554.  
  555.     exit(0);
  556.     }
  557.  
  558. lsdfact(n){
  559.     int    a[10];
  560.     int    i;
  561.     int    n5;
  562.     int    tmp;
  563.  
  564.     for(i=0;i<=9;i++)a[i]=alpha(i,n);
  565.  
  566.     n5=0;
  567. /* NOTE: order is important in following */
  568. l5:;
  569.     while(tmp=a[5]){    /* cancel factors of 5 */
  570.         n5+=tmp;
  571.         a[1]+=(tmp+4)/5;
  572.         a[3]+=(tmp+3)/5;
  573.         a[5]=(tmp+2)/5;
  574.         a[7]+=(tmp+1)/5;
  575.         a[9]+=(tmp+0)/5;
  576.         }
  577. l10:;
  578.     if(tmp=a[0]){
  579.         a[0]=0;    /* cancel all factors of 10 */
  580.         for(i=0;i<=9;i++)a[i]+=alpha(i,tmp);
  581.         }
  582.     if(a[5]) goto l5;
  583.     if(a[0]) goto l10;
  584.  
  585. /* n5 == number of 5's cancelled;
  586.    must now cancel same number of factors of 2 */
  587.     i=ipow(2,a[2]+2*a[4]+a[6]+3*a[8]-n5)*
  588.         ipow(3,a[3]+a[6]+2*a[9])*
  589.         ipow(7,a[7]);
  590.     assert(i%10);    /* must not be zero */
  591.     return    i%10;
  592.     }
  593.  
  594. alpha(d,n){
  595. /* number of decimal numbers in [1,n] ending in digit d */
  596.     int tmp;
  597.     tmp=(n+10-d)/10;
  598.     if(d==0)tmp--;    /* forget 0 */
  599.     return tmp;
  600.     }
  601.  
  602. ipow(x,y){
  603. /* x^y mod 10 */
  604.     if(y==0) return 1;
  605.     if(y==1) return x;
  606.     return p[x-2][(y-1)%4];
  607.     }
  608.  
  609.  
  610.  
  611.  
  612. ==> arithmetic/digits/zeros/million.p <==
  613. How many zeros occur in the numbers from 1 to 1,000,000?
  614.  
  615. ==> arithmetic/digits/zeros/million.s <==
  616. In the numbers from 10^(n-1) through 10^n - 1, there are 9 * 10^(n-1)
  617. numbers of n digits each, so 9(n-1)10^(n-1) non-leading digits, of
  618. which one tenth, or 9(n-1)10^(n-2), are zeroes.  When we change the
  619. range to 10^(n-1) + 1 through 10^n, we remove 10^(n-1) and put in
  620. 10^n, gaining one zero, so
  621.  
  622.     p(n) = p(n-1) + 9(n-1)10^(n-2) + 1 with p(1)=1.
  623.  
  624. Solving the recurrence yields the closed form
  625.  
  626.     p(n) = n(10^(n-1)+1) - (10^n-1)/9.
  627.  
  628. For n=6, there are 488,895 zeroes, 600,001 ones, and 600,000 of all other
  629. digits.
  630.  
  631. ==> arithmetic/magic.squares.p <==
  632. Are there large squares, containing only consecutive integers, all of whose
  633. rows, columns and diagonals have the same sum?  How about cubes?
  634.  
  635. ==> arithmetic/magic.squares.s <==
  636. Here is an 8x8 example:
  637.  
  638. 01 56 48 25 33 24 16 57
  639. 63 10 18 39 31 42 50 07
  640. 62 11 19 38 30 43 51 06
  641. 04 53 45 28 36 21 13 60
  642. 05 52 44 29 37 20 12 61
  643. 59 14 22 35 27 46 54 03
  644. 58 15 23 34 26 47 55 02
  645. 08 49 41 32 40 17 09 64
  646.  
  647. References:
  648.     "Magic Squares and Cubes"
  649.     W.S. Andrews
  650.     The Open Court Publishing Co.
  651.     Chicago, 1908
  652.  
  653.     "Mathematical Recreations"
  654.     M. Kraitchik
  655.     Dover
  656.     New York, 1953
  657.  
  658.  
  659.  
  660.  
  661. ==> arithmetic/pell.p <==
  662. Find integer solutions to x^2 - 92y^2 = 1.
  663.  
  664. ==> arithmetic/pell.s <==
  665. x=1        y=0
  666. x=1151     y=120
  667. x=2649601  y=276240
  668. etc.
  669.  
  670. Each successive solution is about 2300 times the previous
  671. solution;  they are every 8th partial fraction (x=numerator,
  672. y=denominator) of the continued fraction for sqrt(92) =
  673. [9,  1,1,2,4,2,1,1,18,  1,1,2,4,2,1,1,18,  1,1,2,4,2,1,1,18, ...]
  674.  
  675. Once you have the smallest positive solution (x1,y1) you
  676. don't need to "search" for the rest.  You can obtain the nth positive
  677. solution (xn,yn) by the formula
  678.  
  679. (x1 + y1 sqrt(92))^n = xn + yn sqrt(92).
  680.  
  681. See Niven & Zuckerman's An Introduction to the Theory of Numbers.
  682. Look in the index under Pell's equation.
  683.  
  684. ==> arithmetic/prime/arithmetic.progression.p <==
  685. Is there an arithmetic progression of 20 or more primes?
  686.  
  687. ==> arithmetic/prime/arithmetic.progression.s <==
  688. There is an arithmetic progression of 21 primes:
  689.     142072321123 + 1419763024680 i, 0 <= i < 21.
  690.  
  691. It was discovered on 30 November 1990, by programs running in the background
  692. on a network of Sun 3 workstations in the Department of Computer Science,
  693. University of Queensland, Australia.
  694.  
  695. See: Andrew Moran and Paul Pritchard, The design of a background job
  696. on a local area network, Procs. 14th Australian Computer Science Conference,
  697. 1991, to appear.
  698.  
  699. ==> arithmetic/prime/consecutive.composites.p <==
  700. Are there 10,000 consecutive non-prime numbers?
  701.  
  702. ==> arithmetic/prime/consecutive.composites.s <==
  703. 9973!+2 through 9973!+10006 are composite.
  704.  
  705. ==> arithmetic/sequence.p <==
  706. Prove that all sets of n integers contain a subset whose sum is divisible by n.
  707.  
  708. ==> arithmetic/sequence.s <==
  709. Consider the set of remainders of the partial sums a(1) + ... + a(i).
  710. Since there are n such sums, either one has remainder zero (and we're
  711. thru) or 2 coincide, say the i'th and j'th.  In this case, a(i+1) +
  712. ... + a(j) is divisible by n.  (note this is a stronger result since
  713. the subsequence constructed is of *adjacent* terms.)  Consider a(1)
  714. (mod n), a(1)+a(2) (mod n), ..., a(1)+...+a(n) (mod n).  Either at
  715. some point we have a(1)+...+a(m) = 0 (mod n) or else by the pigeonhole
  716. principle some value (mod n) will have been duplicated.  We win either
  717. way.
  718.  
  719. ==> arithmetic/sum.of.cubes.p <==
  720. Find two fractions whose cubes total 6.
  721.  
  722. ==> arithmetic/sum.of.cubes.s <==
  723. Restated:
  724. Find X, Y, minimum Z (all positive integers) where
  725. (X/Z)^3 + (Y/Z)^3 = 6
  726.  
  727. Again, a generalized solution would be nice.
  728.  
  729. You are asking for the smallest z s.t. x^3 + y^3 = 6*z^3 and x,y,z in Z+.
  730. In general, questions like these are extremely difficult; if you're
  731. interested take a look at books covering Diophantine equations
  732. (especially Baker's work on effective methods of computing solutions).
  733.  
  734. Dudeney mentions this problem in connection with #20 in _The Canterbury
  735. Puzzles_; the smallest answer is (17/21)^3 + (37/21)^3 = 6.
  736.  
  737. For the interest of the readers of this group I'll quote:
  738.  
  739.    "Given a known case for the expression of a number as the sum or
  740. difference of two cubes, we can, by formula, derive from it an infinite
  741. number of other cases alternately positive and negative.  Thus Fermat,
  742. starting from the known case 1^3 + 2^3 = 9 (which we will call a
  743. fundamental case), first obtained a negative solution in bigger
  744. figures, and from this his positive solution in bigger figures still.
  745. But there is an infinite number of fundamentals, and I found by trial
  746. a negative fundamental solution in smaller figures than his derived
  747. negative solution, from which I obtained the result shown above.  That
  748. is the simple explanation."
  749.  
  750. In the above paragraph Dudeney is explaining how he derived (*by hand*)
  751. that (415280564497/348671682660)^3 + (676702467503/348671682660)^3 = 9.
  752.  
  753. He continues:
  754.  
  755. "We can say of any number up to 100 whether it is possible or not to
  756. express it as the sum of two cubes, except 66.  Students should read
  757. the Introduction to Lucas's _Theorie des Nombres_, p. xxx."
  758.  
  759. "Some years ago I published a solution for the case 6 = (17/21)^3 +
  760. (37/21)^3, of which Legendre gave at some length a 'proof' of
  761. impossibility; but I have since found that Lucas anticipated me in
  762. a communication to Sylvester."
  763.  
  764. ==> arithmetic/tests.for.divisibility/eleven.p <==
  765. What is the test to see if a number is divisible by eleven?
  766.  
  767.  
  768. ==> arithmetic/tests.for.divisibility/eleven.s <==
  769. If the alternating sum of the digits is divisible by eleven, so is the number.
  770.  
  771. For example, 1639 leads to 9 - 3 + 6 - 1 = 11, so 1639 is divisible by 11.
  772.  
  773. Proof:
  774. Every integer n can be expressed as
  775. n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1
  776. where a1, a2, a3, ...a_k+1 are integers between 0 and 9.
  777. 10 is congruent to -1 mod(11).
  778. Thus if (-1^k)*a1 + (-1^k-1)*a2 + ...+ (a_k+1) is congruent to 0mod(11) then
  779. n is divisible by 11.
  780.  
  781. ==> arithmetic/tests.for.divisibility/nine.p <==
  782. What is the test to see if a number is divisible by nine?
  783.  
  784. ==> arithmetic/tests.for.divisibility/nine.s <==
  785. If the sum of the digits is divisible by nine, so is the number.
  786.  
  787. Proof:
  788. Every integer n can be expressed as
  789. n = a1*(10^k) + a2*(10^k-1)+ .....+ a_k+1
  790. where a1, a2, a3, ...a_k+1 are integers between 0 and 9.
  791. Note that 10 is congruent to 1 (mod 9). Thus 10^k is congruent to 1 (mod 9) for
  792. every k >= 0.
  793. Thus n is congruent to (a1+a2+a3+....+a_k+1) mod(9).
  794. Hence (a1+a2+...+a_k+1) is divisible by 9 iff n is divisible by 9.
  795.